import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/24 9:55
 * @description 01字典树 离线版，不全部插入字典树，而是将满足条件的数插入
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 3, 4};
        int[][] qu = {{3, 1}, {1, 3}, {5, 6}};
        Solution solution = new Solution();
        solution.maximizeXor(nums, qu);
    }

    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int numQ = queries.length;
        int[][] newQueries = new int[numQ][3];
        for (int i = 0; i < numQ; ++i) {
            newQueries[i][0] = queries[i][0];
            newQueries[i][1] = queries[i][1];
            // 记住排序前的查询位置
            newQueries[i][2] = i;
        }
        // 将查询按不超过m的大小升序排序
        Arrays.sort(newQueries, (query1, query2) -> query1[1] - query2[1]);

        int[] ans = new int[numQ];
        Trie trie = new Trie();
        int idx = 0, n = nums.length;
        for (int[] query : newQueries) {
            int x = query[0], m = query[1], qid = query[2];
            // 将所有小于等于m的数加入字典树后，再查询
            while (idx < n && nums[idx] <= m) {
                trie.insert(nums[idx]);
                ++idx;
            }
            if (idx == 0) {
                // 字典树为空
                ans[qid] = -1;
            } else {
                ans[qid] = trie.getMaxXor(x);
            }
        }
        return ans;
    }
}

class Trie {
    static final int L = 30;
    /**
     * children[0]表示左节点，[1]表示右节点
     */
    Trie[] children = new Trie[2];

    public void insert(int val) {
        Trie node = this;
        for (int i = L; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new Trie();
            }
            node = node.children[bit];
        }
    }

    public int getMaxXor(int val) {
        int ans = 0;
        Trie node = this;
        for (int i = L; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node.children[bit ^ 1] != null) {
                ans |= 1 << i;
                bit ^= 1;
            }
            node = node.children[bit];
        }
        return ans;
    }
}
